package site.wanjiahao;

public class BruteForce {

    // 蛮力算法优化2
    // pi = ''pi + ti''
    static int indexOf(String text, String pattern) {
        if (text == null || pattern == null ||
                text.isEmpty() || pattern.isEmpty() ||
                pattern.length() > text.length()) return -1;

        char[] texts = text.toCharArray();
        char[] patterns = pattern.toCharArray();
        // 模式串初始索引
        int pi = 0;
        int pln = pattern.length();
        // 匹配串初始索引
        int ti = 0;
        int tln = text.length();
        int tMax = tln - pln;
        for (; pi < pln && ti <= tMax; pi++) {
            if (texts[ti + pi] == patterns[pi]) continue;
            // 不相等
            pi = 0;
            ti++;
        }
        return pi == pln ? ti: -1;
    }

    // 蛮力算法，优化1
    static int indexOf2(String text, String pattern) {
        if (text == null || pattern == null ||
                text.isEmpty() || pattern.isEmpty() ||
                pattern.length() > text.length()) return -1;

        char[] texts = text.toCharArray();
        char[] patterns = pattern.toCharArray();
        // 模式串初始索引
        int pi = 0;
        int pln = pattern.length();
        // 匹配串初始索引
        int ti = 0;
        int tln = text.length();
        while (pi < pln && ti - pi <= tln - pln) {
            if (texts[ti] == patterns[pi]) {
                // 当前字符相等
                ti++;
                pi++;
            } else {
                // 不相等
                pi = 0;
                ti -= pi - 1;
            }
        }
        return pi == pln ? ti - pi: -1;
    }

    // 蛮力算法
    static int indexOf1(String text, String pattern) {
        if (text == null || pattern == null ||
                text.isEmpty() || pattern.isEmpty() ||
                pattern.length() > text.length()) return -1;

        char[] texts = text.toCharArray();
        char[] patterns = pattern.toCharArray();
        // 模式串初始索引
        int pi = 0;
        int pln = pattern.length();
        // 匹配串初始索引
        int ti = 0;
        int tln = text.length();
        while (pi < pln && ti < tln) {
            if (texts[ti] == patterns[pi]) {
                // 当前字符相等
                ti++;
                pi++;
            } else {
                // 不相等
                pi = 0;
                ti -= pi - 1;
            }
        }
        return pi == pln? ti - pi: -1;
    }


}
